๋ฌธ์
Programmers - ํ ํธ์ง
๐ Logic
private void init() {
for (int i = 0; i < n; i++) {
pre[i] = i - 1;
next[i] = i + 1;
}
next[n - 1] = -1;
}
- ํ์ฌ node์ ์ด์ ๊ณผ ์ดํ node๋ฅผ ์ ์ฅํ๊ธฐ ์ํ ๋ฐฐ์ด์ ์ด๊ธฐํํ๋ค.
public void delete() {
trash.push(new Node(now, pre[now], next[now]));
// now์ pre์ next๋ฅผ updateํจ์ผ๋ก์จ ํด๋น node๋ฅผ ์ ๊ฑฐ
if (pre[now] != -1) next[pre[now]] = next[now];
if (next[now] != -1) pre[next[now]] = pre[now];
// ํด๋น ์์น๋ ์๋ณธ๊ณผ ๋ฌ๋ผ์ง๋ฏ๋ก X๋ก ๋ณ๊ฒฝ
sb.setCharAt(now, 'X');
// now ์ด๋
if(next[now] != -1) now = next[now];
else now = pre[now];
}
public void undo() {
Node insert = trash.pop();
// ๋ค์ ์ถ๊ฐํ insert node์ pre์ next๋ฅผ updateํจ์ผ๋ก์จ ํด๋น node๋ฅผ ์ถ๊ฐ
if (insert.before != -1) next[insert.before] = insert.cur;
if (insert.after != -1) pre[insert.after] = insert.cur;
// ์์๋ณต๊ตฌ
sb.setCharAt(insert.cur, 'O');
}
goUp() ๊ณผ goDown() ์ผ๋ก now ๋ฅผ ๊ณ์ ์ต์ ํํ๊ณ , ์ญ์ ๋ฐ ๋ณต๊ตฌ ์์๋ pre ์ next ๋ฐฐ์ด์ ์
๋ฐ์ดํธํ๋ ๋ฐฉ์์ ์ฌ์ฉํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Node {
int cur;
int before;
int after;
public Node(int cur, int before, int after) {
this.cur = cur;
this.before = before;
this.after = after;
}
}
class Table {
StringBuilder sb;
Stack<Node> trash = new Stack<>();
// ํ์ฌ node์ ์ด์ ๊ณผ ์ดํ node๋ฅผ ์ ์ฅํ ๋ฐฐ์ด
int[] pre;
int[] next;
int n;
int now;
public Table(int n, int now) {
this.n = n;
this.now = now;
pre = new int[n];
next = new int[n];
sb = new StringBuilder("O".repeat(n));
init();
}
private void init() {
for (int i = 0; i < n; i++) {
pre[i] = i - 1;
next[i] = i + 1;
}
next[n - 1] = -1;
}
// ์ค๊ฐ์ ์ญ์ ๋ node๊ฐ ์์ ์ ์๊ธฐ์ n๋งํผ ๋ฐ๋ณตํ๋ฉด์ now ์ด๋
public void goUp(int n) {
while(n-- > 0) now = pre[now];
}
public void goDown(int n) {
while(n-- > 0) now = next[now];
}
public void delete() {
trash.push(new Node(now, pre[now], next[now]));
// now์ pre์ next๋ฅผ updateํจ์ผ๋ก์จ ํด๋น node๋ฅผ ์ ๊ฑฐ
if (pre[now] != -1) next[pre[now]] = next[now];
if (next[now] != -1) pre[next[now]] = pre[now];
// ํด๋น ์์น๋ ์๋ณธ๊ณผ ๋ฌ๋ผ์ง๋ฏ๋ก X๋ก ๋ณ๊ฒฝ
sb.setCharAt(now, 'X');
// now ์ด๋
if(next[now] != -1) now = next[now];
else now = pre[now];
}
public void undo() {
Node insert = trash.pop();
// ๋ค์ ์ถ๊ฐํ insert node์ pre์ next๋ฅผ updateํจ์ผ๋ก์จ ํด๋น node๋ฅผ ์ถ๊ฐ
if (insert.before != -1) next[insert.before] = insert.cur;
if (insert.after != -1) pre[insert.after] = insert.cur;
// ์์๋ณต๊ตฌ
sb.setCharAt(insert.cur, 'O');
}
public String print() {
return sb.toString();
}
}
class Solution {
public String solution(int n, int k, String[] cmd) {
Table t = new Table(n, k);
for (String c : cmd) {
switch (c.charAt(0)) {
case 'U' -> t.goUp(Integer.parseInt(c.substring(2)));
case 'D' -> t.goDown(Integer.parseInt(c.substring(2)));
case 'C' -> t.delete();
case 'Z' -> t.undo();
}
}
// ์ต์ข
์ ์ผ๋ก ํ๋ฅผ ๋น๊ตํ์ฌ answer๋ฅผ ์์ฑํ๋ method
return t.print();
}
}
โ๏ธ Review
- ์ฒ์ ๊ตฌํ์
List ์ Stack ์ ์ด์ฉํ๋ค. ์คํจํ ํ
์ผ๊ฐ ๋๋ฌด ๋ง์๊ณ , ํจ์จ์ฑ์ ์์ ๋์๊ฐ์ง๋ ์์๋ค.
- ์์์ ์ฝ์
๊ณผ ์ญ์ ๊ฐ ์์ฃผ ์ผ์ด๋๊ธฐ์, ์ด์ ์ ํฉํ ์๋ฃ๊ตฌ์กฐ๊ฐ ํ์ํ ๊ฒ ๊ฐ์๋ค. ์ด์๋
LinkedList ๊ฐ ์ ํฉํด๋ณด์๋ค.
- ์๊ฐ๋ณด๋ค ์ฌ์๋ณด์์ผ๋, ๊ตฌํํ ์๋ก ๊ผผ๊ผผํ ์๊ฐํด์ผ ํ ๊ตฌํ๋ถ๋ค์ด ์๊ฒจ๋, ์ฐธ๊ณ ๊ฐ ํ์ํ๋ค...